0% completed
In this lesson, we’ll practice analyzing time complexity using two basic algorithms: finding the maximum element in a list and Insertion Sort. Both examples will reinforce the process of breaking down an algorithm and identifying the time complexity.
Example 1: Finding the Maximum Element in a List
Let’s start with a simple algorithm to find the maximum element in a list of n numbers.
Algorithm Code
Step-by-Step Analysis
-
Initialization:
max_num = numbers[0]- This assignment is constant and takes
time.
- This assignment is constant and takes
-
Loop through the List:
for num in numbers- The loop runs once for each element in the list, making it
because we’re visiting every element once.
- The loop runs once for each element in the list, making it
-
Conditional Check:
if num > max_num- Inside the loop, the
ifstatement checks each element. Since this check is executed in each iteration, it contributesto the time complexity.
- Inside the loop, the
-
Assignment Inside Loop:
max_num = num- The assignment only happens when the condition is true. However, it’s still part of the loop, so we consider its complexity as
overall.
- The assignment only happens when the condition is true. However, it’s still part of the loop, so we consider its complexity as
Total Time Complexity
Adding all these steps together, we get:
- Initialization:
- Loop (including conditional check and assignment):
Since find_max algorithm is
Example 2: Insertion Sort
Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It’s useful for small or nearly sorted data but can be inefficient for larger lists.
Algorithm Code
Step-by-Step Analysis
Let’s break down each part of the code and analyze its time complexity.
-
Outer Loop:
for i in range(1, len(arr))- This loop runs from the second element (index 1) to the last element of
arr, so it iteratesn - 1times (wherenis the length of the array). - The outer loop contributes a time complexity of
.
- This loop runs from the second element (index 1) to the last element of
-
Inner Loop:
while j >= 0 and arr[j] > key- The inner
whileloop comparesarr[j]tokeyand shifts elements if they are larger thankey. - In the worst case, the
whileloop can runitimes for eachiin the outer loop, especially if the list is in reverse order. - On average, for each element, it runs half of
itimes, resulting in time complexity contributions for each outer loop iteration.
- The inner
-
Total Time Complexity
To understand the full time complexity, let’s examine different cases:
- When the array is in reverse order, each element is compared with all the previous elements. This results in a maximum of
comparisons. - This sum simplifies to approximately
, giving us a time complexity of .
- When the array is in reverse order, each element is compared with all the previous elements. This results in a maximum of
In the next lesson, Best, Worst, and Average Cases, we’ll explore how different inputs affect the performance of algorithms like insertion sort.
On this page
Example 1: Finding the Maximum Element in a List
Algorithm Code
Step-by-Step Analysis
Example 2: Insertion Sort
Algorithm Code
Step-by-Step Analysis